package LeetCode.LC39;

/**
 * @author corn
 * @create 2020-08-13-20:11
 */

import java.util.*;

/**
 * 39. 组合总和
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的数字可以无限制重复被选取。
 * 说明：
 *     所有数字（包括 target）都是正整数。
 *     解集不能包含重复的组合。
 */
public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int len = candidates.length;
        // 排序是为了提前终止搜索
        Arrays.sort(candidates);
        dfs(candidates, target, 0, new ArrayDeque<>(), res);
        return res;
    }

    /**
     * @param candidates 数组输入
     * @param residue    剩余数值
     * @param begin      本轮搜索的起点下标
     * @param path       从根结点到任意结点的路径   Deque:双端队列
     * @param res        结果集变量
     */
    private void dfs(int[] candidates ,int residue ,int begin ,Deque<Integer> path ,List<List<Integer>> res) {
        //1. 判断是否满足要求
        if (residue == 0) {
            // 由于 path 全局只使用一份，到叶子结点的时候需要做一个拷贝
            res.add(new ArrayList<>(path));
            return;
        }
        //2. 其次从各个字符开始往下面搜索
        for (int i = begin; i < candidates.length; i++) {

            // 由于数组是有序的，所以不用继续判断下去，直接退出剪枝
            if (residue < candidates[i]) {
                break;
            }
            path.addLast(candidates[i]);
            //继续向下搜索：此时i不变，满足了 “数字可以无限制重复被选取” 的条件
            dfs(candidates, residue - candidates[i], i, path, res);
            //回溯，将path最后一个数踢出。
            path.removeLast();
        }
    }
}
